/**
 * @file 009.乘积小于K的子数组.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-07
 *
 * @copyright Copyright (c) 2021
 *
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    int numSubarrayProductLessThanK(vector<int> &nums, int k)
    {
        // 暴力
#if 0
        int n = nums.size();
        int cnt = 0;
        for (int i = 0; i < n; ++i){
            int j = i;
            int multi = 1;
            while (j < n){
                multi *= nums[j++];
                if (multi >= k){
                    break;
                }
                ++cnt;
            }
        }
        return cnt;
#endif
        // 滑窗
        if (k <= 1) {
            return 0;
        }
        int n = nums.size();
        int cnt = 0;
        int multi = 1;
        int i = 0;
        for (int j = 0; j < n; ++j) {
            multi *= nums[j];
            while (multi >= k) {
                multi /= nums[i++];
            }
            cnt += j - i + 1;
        }
        return cnt;
    }
};

int main()
{
    vector<int> nums1 = {10, 5, 2, 6};
    cout << Solution().numSubarrayProductLessThanK(nums1, 100) << endl;
    vector<int> nums2 = {1, 2, 3};
    cout << Solution().numSubarrayProductLessThanK(nums2, 0) << endl;
    return 0;
}